package com.tgy.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @Author: tgy
 * @Date: 12/7/20 11:23 AM
 *
 * https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
 */
public class 剑指_Offer_07_重建二叉树_01 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        if (preorder == null || inorder == null || preorder.length != inorder.length) {

            return null;
        }

        Map<Integer, Integer> locations = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {

            locations.put(inorder[i],i);
        }

        return generalTree(preorder,0,preorder.length,inorder,0,inorder.length,locations);
    }

    private TreeNode generalTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer,Integer> locations) {

        if (preStart >= preEnd) {

            return null;
        }

        int curElement = preorder[preStart];
        TreeNode rootNode = new TreeNode(curElement);

        if (preEnd - preStart == 1) {

            return rootNode;
        }else {

            Integer index = locations.get(curElement);
            rootNode.left = generalTree(preorder,preStart + 1,preStart + (index - inStart) + 1,inorder,inStart,index,locations);
            rootNode.right = generalTree(preorder,preStart + (index - inStart) + 1,preEnd,inorder,index + 1,inEnd,locations);
        }

        return rootNode;
    }


}
